package com.xieyong.leetcode;

public class Leetcode2040 {
    public static void main(String[] args) {
        Leetcode2040 leetcode2040 = new Leetcode2040();
        int[] nums1 = {2,5};
        int[] nums2 = {3,4};
        long k = 2;
        long l = leetcode2040.kthSmallestProduct(nums1, nums2, k);
        System.out.println(l);

    }


    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {
        int n = nums1.length;
        long left = (long) -10e10, right = (long) 10e10;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long count = 0;
            for (int i = 0; i < n; i++) {
                count += countLowMid(nums2, nums1[i], mid);
            }
            if (count >= k) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private long countLowMid(int[] nums2, long x, long v) {
        int n = nums2.length;
        long count = 0;
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            long prod = (long) nums2[mid] * x;
            if ((x >= 0 && prod <= v) || (x < 0 && prod > v)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if (x >= 0) {
            return left;
        } else {
            return n - left;
        }
    }
}
